package backtrack;

import java.util.*;

/**
 * @author gaolainan
 */
public class CombinationSumTwo
{
    static LinkedList<LinkedList<Integer>> res = new LinkedList<>();
    public static void main(String[] args)
    {
        CombinationSumTwo combinationSumTwo = new CombinationSumTwo();
        int[] arr = {9};
        int target = 4;
        combinationSumTwo.combinationSum2(arr, target);
        System.out.println(res.size());
    }



    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        LinkedList<Integer> tmp = new LinkedList<>();
        backtrack(candidates, target, tmp);
        return new ArrayList<>(res);
    }

    public void backtrack(int[] arr,  int target,LinkedList<Integer> tmp){
        if (target < 0){
            return;
        }
        if (target == 0){
            res.add(new LinkedList<>(tmp));
            return;
        }

        for (int i = 0;i < arr.length;i++){
            tmp.add(arr[i]);
            backtrack(arr, target-arr[i], tmp);
            tmp.removeLast();
        }
    }
}
